package simulation;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
//todo simulation method timeout ,可以模拟等差数列
public class EliminationGame390 {
    public int lastRemaining(int n) {
        List<Integer> simulation = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            simulation.add(i);
        }
        boolean left = true;
        while (simulation.size()!=1){
            List<Integer> temp = new ArrayList<>();
            if(left){
                for (int i = 0; i < simulation.size(); i = i+2) {
                    temp.add(simulation.get(i));
                }
            }else {
                for (int i = simulation.size()-1; i >=0 ; i=i-2) {
                    temp.add(simulation.get(i));
                }
            }
            left=!left;
            for (int i = 0; i < temp.size(); i++) {
                simulation.remove(temp.get(i));
            };
        }
        return simulation.get(0)+1;
    }
}
